package algorithm

func QuickSort(arr []int) {
	//if len(arr) <= 1 {
	//	return
	//}
	//i, j := 0, len(arr)-1
	//k, v := 0, arr[0]
	//flag := true
	//for i < j {
	//	if flag {
	//		//从右往左找比v大的值，找到交换顺序
	//		if arr[j] < v {
	//			arr[j], arr[k] = arr[k], arr[j]
	//			k = j
	//			v = arr[k]
	//			flag = !flag
	//		} else {
	//			j--
	//		}
	//	} else {
	//		//从做往右找比v小的值，找到交换顺序
	//		if arr[i] > v {
	//			arr[i], arr[k] = arr[k], arr[i]
	//			k = i
	//			v = arr[k]
	//			flag = !flag
	//		} else {
	//			i++
	//		}
	//	}
	//}
	//QuickSort(arr[:i])
	//QuickSort(arr[i+1:])
	//return
	qsort1(arr, 0, len(arr)-1)
}

//单向扫描
func partition1(arr []int, l, h int) int {
	x := arr[h]
	i := l - 1
	for j := l; j < h; j++ {
		if arr[j] <= x {
			i += 1
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[h] = arr[h], arr[i+1]
	return i + 1
}

//单向扫描
func partition2(arr []int, l, h int) int {
	x := arr[h]
	i := l
	for j := l; j < h; j++ {
		if arr[j] <= x {
			if i != j {
				arr[i], arr[j] = arr[j], arr[i]
			}
			i += 1
		}
	}
	arr[i], arr[h] = arr[h], arr[i]
	return i
}

//双向扫描
func partition3(arr []int, l, h int) int {
	x := arr[l]
	i := l + 1
	j := h
	for {
		for i <= j && arr[j] >= x {
			j--
		}
		if i > j {
			break
		}
		for i <= j && arr[i] < x {
			i++
		}
		if i > j {
			break
		}
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
	arr[l], arr[j] = arr[j], arr[l]
	return j
}

//双向扫描
func partition4(arr []int, l, h int) int {
	x := arr[h]
	i := l
	j := h - 1
	for {
		for i <= j && arr[i] <= x {
			i++
		}
		if i > j {
			break
		}
		for i <= j && arr[j] > x {
			j--
		}
		if i > j {
			break
		}
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
	arr[h], arr[i] = arr[i], arr[h]
	return i
}

func qsort1(arr []int, l, h int) {
	if l < h {
		n := partition4(arr, l, h)
		qsort1(arr, l, n-1)
		qsort1(arr, n+1, h)
	}

}
